package com.gxc.stack;

import java.util.Stack;

/**
 * 栈逆序
 *
 * 给定一个栈，请逆序这个栈，不能申请额外的数据结构，只能使用递归函数
 *
 * 解法：
 * 递归获取栈中最后一个元素，然后弹出，然后递归调用自己，直到栈为空，然后把元素依次压入栈中
 */
public class StackReverse {

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(3);
        stack.push(2);
        stack.push(1);

        //printStack(stack);

        System.out.println("--------------");
        reserve(stack);
        printStack(stack);
    }

    private static void printStack(Stack<Integer> stack) {
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }


    private static int getLast(Stack<Integer> stack) {
        int result = stack.pop();
        if (stack.isEmpty()) {
            return result;
        } else {
            int last = getLast(stack);
            //其余重新压入栈中，保持顺序
            stack.push(result);
            return last;
        }
    }

    private static void reserve(Stack<Integer> stack) {
        if (stack.isEmpty()) return;

        int last = getLast(stack);
        reserve(stack);
        stack.push(last);
    }

}
